#include <cstdio>
#include <cstring>
#include <queue>

const int N = 205;
int n, k, s, t;
int e_cnt = 1, heads[N], cur[N], h[N];
char map[N][N];

struct Edge {
  int v, nxt, flow;
} e[(N * N) << 1];

inline void add(int u, int v, int f) {
  e[++e_cnt].v = v, e[e_cnt].nxt = heads[u], heads[u] = e_cnt, e[e_cnt].flow = f;
  e[++e_cnt].v = u, e[e_cnt].nxt = heads[v], heads[v] = e_cnt, e[e_cnt].flow = 0;
}

inline bool bfs() {
  std::queue<int> q;
  q.push(s);
  memset(h, 0, sizeof(h));
  h[s] = 1;
  cur[s] = heads[s];
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = heads[u], v; i; i = e[i].nxt) {
      if (!h[v = e[i].v] && e[i].flow) {
        h[v] = h[u] + 1;
        cur[v] = heads[v];
        q.push(v);
        if (v == t) return true;
      }
    }
  }
  return false;
}

int dinic(int x, int flow) {
  if (x == t) return flow;
  int rest = flow, k;
  for (int i = cur[x], v; i && rest; i = e[i].nxt) {
    if (h[v = e[i].v] == h[x] + 1 && e[i].flow) {
      k = dinic(v, std::min(e[i].flow, rest));
      if (!k) h[v] = 0;
      cur[x] = i;
      e[i].flow -= k;
      e[i ^ 1].flow += k;
      rest -= k;
    }
  }
  return flow - rest;
}

inline void add_edge(int x) {
  e_cnt = 1;
  memset(heads, 0, sizeof(heads));
  for (int i = 1; i <= n; ++i) {
    add(s, i, x);
    add(i + n + n, t, x);
    add(i, i + n, k);
    add(i + n + (n << 1), i + (n << 1), k);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (map[i][j] == 'Y') {
        add(i, j + (n << 1), 1);
      } else {
        add(i + n, j + n + (n << 1), 1);
      }
    }
  }
}

inline bool check(int x) {
  add_edge(x);
  int ans = 0, flow;
  while (bfs()) {
    if ((flow = dinic(s, 0x3fffffff))) ans += flow;
  }
  return ans == x * n;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
  freopen("P3153 [CQOI2009]跳舞.in", "r", stdin);
  freopen("P3153 [CQOI2009]跳舞.out", "w", stdout);
#endif
#endif

  scanf("%d%d", &n, &k);
  s = 0, t = (n << 2) + 1;
  for (int i = 1; i <= n; ++i) {
    scanf("%s", map[i] + 1);
  }
  int l = 0, r = n, mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid)) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  printf("%d", l - 1);
  return 0;
}